#! /usr/bin/python3
# -*- coding: UTF-8 -*-
  
'''※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
File Name: blockchain.py
Author: GID5564
Description: 区块链
Version: 1.0
Created Time: 27/11/24-09:25:42
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※'''

# 中国剩余定理：
# GCD（最大公约数）或 HCF（最高公因数）

# 如果 GCD(a,b) = 1，那么对于任何余数 ra modulo a 和任何余数 rb modulo b 存在整数 n，
# 使得 n = ra (mod a) 且 n = rb (mod b)。如果 n1 和 n2 是两个这样的整数，则 n1 = n2 (mod ab)

# 算法：

# 1. 使用扩展欧几里得算法找到 x, y 使得 a*x + b*y = 1
# 2. 取 n = ra*by + rb*ax

# 扩展欧几里得算法
def extended_euclid(a, b):
    """
    >>> extended_euclid(10, 6)
    (-1, 2)

    >>> extended_euclid(7, 5)
    (-2, 3)

    """
    if b == 0:
        return (1, 0)
    (x, y) = extended_euclid(b, a % b)
    k = a // b
    return (y, x - k * y)

# 使用扩展欧几里得算法找到逆元
def chinese_remainder_theorem(n1, r1, n2, r2):
    """
    >>> chinese_remainder_theorem(5,1,7,3)
    31

    解释：31 是最小的数字，满足以下条件：
          (i) 当我们用它除以 5 时，余数为 1
          (ii) 当我们用它除以 7 时，余数为 3

    >>> chinese_remainder_theorem(6,1,4,3)
    14

    """
    (x, y) = extended_euclid(n1, n2)
    m = n1 * n2
    n = r2 * x * n1 + r1 * y * n2
    return (n % m + m) % m

# ----------使用 InvertModulo 而不是 ExtendedEuclid 的相同解决方案----------------

# 此函数找到 a 的逆元，即 a^(-1)
def invert_modulo(a, n):
    """
    >>> invert_modulo(2, 5)
    3

    >>> invert_modulo(8,7)
    1

    """
    (b, x) = extended_euclid(a, n)
    if b < 0:
        b = (b % n + n) % n
    return b

# 使用 InvertingModulo 的相同解决方案
def chinese_remainder_theorem2(n1, r1, n2, r2):
    """
    >>> chinese_remainder_theorem2(5,1,7,3)
    31

    >>> chinese_remainder_theorem2(6,1,4,3)
    14

    """
    x, y = invert_modulo(n1, n2), invert_modulo(n2, n1)
    m = n1 * n2
    n = r2 * x * n1 + r1 * y * n2
    return (n % m + m) % m
"""
#例:

# 导入 testmod 用于测试我们的函数
from doctest import testmod

if __name__ == "__main__":
    testmod(name="chinese_remainder_theorem", verbose=True)
    testmod(name="chinese_remainder_theorem2", verbose=True)
    testmod(name="invert_modulo", verbose=True)
    testmod(name="extended_euclid", verbose=True)
    
"""
    
    
# : 给定整数a，B，C（a和B中至少有一个！=0），不定方程#a*X+B*y=C有解（其中X和y是整数）当且仅当GCD（a，B）整除C。
# GCD（最大公约数）或HCF（最高公约数）
def diophantine(a, b, c):
    """
    求解一次不定方程 a*x + b*y = c 的一个解。

    参数:
    a (int): 系数a
    b (int): 系数b
    c (int): 常数项c

    返回值:
    tuple: 一个包含两个整数的元组，表示方程的一个解 (x, y)

    示例:
    >>> diophantine(10,6,14)
    (-7.0, 14.0)

    >>> diophantine(391,299,-69)
    (9.0, -12.0)
    """
    assert (
        c % greatest_common_divisor(a, b) == 0
    )  # 确保c能被gcd(a,b)整除
    (d, x, y) = extended_gcd(a, b)  # 使用扩展欧几里得算法求出gcd和对应的x, y
    r = c / d  # 计算比例因子
    return (r * x, r * y)  # 返回最终的解

# Lemma : if n|ab and gcd(a,n) = 1, then n|b.

# Finding All solutions of Diophantine Equations:

# Theorem : Let gcd(a,b) = d, a = d*p, b = d*q. If (x0,y0) is a solution of Diophantine Equation a*x + b*y = c.
# a*x0 + b*y0 = c, then all the solutions have the form a(x0 + t*q) + b(y0 - t*p) = c, where t is an arbitrary integer.

# n是想要的解的数量，默认为2
def diophantine_all_soln(a, b, c, n=2):
    """
    求解一次不定方程 a*x + b*y = c 的所有解。

    参数:
    a (int): 系数a
    b (int): 系数b
    c (int): 常数项c
    n (int): 想要的解的数量，默认为2

    返回值:
    None: 打印所有解

    示例:
    >>> diophantine_all_soln(10, 6, 14)
    -7.0 14.0
    -4.0 9.0

    >>> diophantine_all_soln(10, 6, 14, 4)
    -7.0 14.0
    -4.0 9.0
    -1.0 4.0
    2.0 -1.0

    >>> diophantine_all_soln(391, 299, -69, n = 4)
    9.0 -12.0
    22.0 -29.0
    35.0 -46.0
    48.0 -63.0
    """
    (x0, y0) = diophantine(a, b, c)  # 初始解
    d = greatest_common_divisor(a, b)  # 计算gcd
    p = a // d  # 计算p
    q = b // d  # 计算q

    for i in range(n):  # 生成n个解
        x = x0 + i * q  # 计算新的x值
        y = y0 - i * p  # 计算新的y值
        print(x, y)  # 打印解

# Euclid's Lemma :  d divides a and b, if and only if d divides a-b and b

# Euclid's Algorithm
def greatest_common_divisor(a, b):
    """
    计算两个整数的最大公约数（GCD）。

    参数:
    a (int): 第一个整数
    b (int): 第二个整数

    返回值:
    int: a和b的最大公约数

    示例:
    >>> greatest_common_divisor(7,5)
    1

    注意: 如果两个整数a和b的最大公约数为1，则称它们互质。
    >>> greatest_common_divisor(121, 11)
    11
    """
    if a < b:  # 确保a大于等于b
        a, b = b, a

    while a % b != 0:  # 使用辗转相除法计算GCD
        a, b = b, a % b

    return b  # 返回GCD

# Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers x and y, then d = gcd(a,b)
def extended_gcd(a, b):
    """
    使用扩展欧几里得算法计算两个整数a和b的GCD以及对应的x和y。

    参数:
    a (int): 第一个整数
    b (int): 第二个整数

    返回值:
    tuple: 一个包含三个整数的元组，表示GCD和对应的x, y

    示例:
    >>> extended_gcd(10, 6)
    (2, -1, 2)

    >>> extended_gcd(7, 5)
    (1, -2, 3)
    """
    assert a >= 0 and b >= 0  # 确保输入的整数非负

    if b == 0:  # 基本情况：如果b为0，则GCD为a，x为1，y为0
        d, x, y = a, 1, 0
    else:  # 递归调用扩展欧几里得算法
        (d, p, q) = extended_gcd(b, a % b)
        x = q  # 更新x值
        y = p - q * (a // b)  # 更新y值

    assert a % d == 0 and b % d == 0  # 确保GCD正确性
    assert d == a * x + b * y  # 确保GCD公式正确性

    return (d, x, y)  # 返回GCD和对应的x, y
"""
# import testmod for testing our function
from doctest import testmod

if __name__ == "__main__":
    testmod(name="diophantine", verbose=True)  # 测试diophantine函数
    testmod(name="diophantine_all_soln", verbose=True)  # 测试diophantine_all_soln函数
    testmod(name="extended_gcd", verbose=True)  # 测试extended_gcd函数
    testmod(name="greatest_common_divisor", verbose=True)  # 测试greatest_common_divisor函数
"""
    
    
    
# 模除算法：
# 一个高效的算法，用于在模数 n 下计算 b 除以 a。

# GCD（最大公约数）或 HCF（最高公因数）

# 给定三个整数 a, b, 和 n，满足 gcd(a,n)=1 且 n>1，该算法应返回一个整数 x，使得
#        0≤x≤n−1，并且 b/a=x(modn)（即 b=ax(modn))。

# 定理：
# a 有模 n 的乘法逆元当且仅当 gcd(a,n) = 1

# 这个函数通过扩展欧几里得算法找到 a 的逆元
def modular_division(a, b, n):
    """
    >>> modular_division(4,8,5)
    2

    >>> modular_division(3,8,5)
    1

    >>> modular_division(4, 11, 5)
    4

    """
    assert n > 1 and a > 0 and greatest_common_divisor(a, n) == 1  # 确保 n>1，a>0，且 gcd(a,n)=1
    (d, t, s) = extended_gcd(n, a)  # 使用扩展欧几里得算法找到 a 的逆元
    x = (b * s) % n  # 计算 x = b * a^(-1) mod n
    return x

# 这个函数找到 a 的逆元，即 a^(-1)
def invert_modulo(a, n):
    """
    >>> invert_modulo(2, 5)
    3

    >>> invert_modulo(8,7)
    1

    """
    (b, x) = extended_euclid(a, n)  # 使用扩展欧几里得算法找到 a 的逆元
    if b < 0:
        b = (b % n + n) % n  # 确保逆元为正数
    return b

# ------------------- 使用 invert_modulo 进行模除运算 -------------------

# 这个函数使用上面的逆元来找到 x = (b*a^(-1))mod n
def modular_division2(a, b, n):
    """
    >>> modular_division2(4,8,5)
    2

    >>> modular_division2(3,8,5)
    1

    >>> modular_division2(4, 11, 5)
    4

    """
    s = invert_modulo(a, n)  # 找到 a 的逆元
    x = (b * s) % n  # 计算 x = b * a^(-1) mod n
    return x

# 扩展欧几里得算法：如果 d 整除 a 和 b，且 d = a*x + b*y 对于整数 x 和 y，则 d = gcd(a,b)
def extended_gcd(a, b):
    """
    >>> extended_gcd(10, 6)
    (2, -1, 2)

    >>> extended_gcd(7, 5)
    (1, -2, 3)

    ** extended_gcd 函数用于输出 d = gcd(a,b)
    """
    assert a >= 0 and b >= 0  # 确保输入非负

    if b == 0:
        d, x, y = a, 1, 0  # 如果 b 为 0，直接返回结果
    else:
        (d, p, q) = extended_gcd(b, a % b)  # 递归调用扩展欧几里得算法
        x = q
        y = p - q * (a // b)  # 更新 x 和 y

    assert a % d == 0 and b % d == 0  # 确保 d 是 a 和 b 的公约数
    assert d == a * x + b * y  # 确保 d = a*x + b*y

    return (d, x, y)

# 扩展欧几里得算法实现
def extended_euclid(a, b):
    """
    >>> extended_euclid(10, 6)
    (-1, 2)

    >>> extended_euclid(7, 5)
    (-2, 3)

    """
    if b == 0:
        return (1, 0)  # 如果 b 为 0，返回 (1, 0)
    (x, y) = extended_euclid(b, a % b)  # 递归调用扩展欧几里得算法
    k = a // b  # 计算商 k
    return (y, x - k * y)  # 更新并返回结果

# 欧几里得引理：d 整除 a 和 b，当且仅当 d 整除 a-b 和 b
# 欧几里得算法实现
def greatest_common_divisor(a, b):
    """
    >>> greatest_common_divisor(7,5)
    1

    注意：在数论中，两个整数 a 和 b 如果只有正整数（因子）1 同时整除它们，则称它们互质，即 gcd(a,b) = 1。

    >>> greatest_common_divisor(121, 11)
    11

    """
    if a < b:
        a, b = b, a  # 确保 a >= b

    while a % b != 0:
        a, b = b, a % b  # 使用欧几里得算法迭代计算 gcd

    return b
"""
#例:
# 导入 doctest 模块用于测试我们的函数
from doctest import testmod

if __name__ == "__main__":
    testmod(name="modular_division", verbose=True)  # 测试 modular_division 函数
    testmod(name="modular_division2", verbose=True)  # 测试 modular_division2 函数
    testmod(name="invert_modulo", verbose=True)  # 测试 invert_modulo 函数
    testmod(name="extended_gcd", verbose=True)  # 测试 extended_gcd 函数
    testmod(name="extended_euclid", verbose=True)  # 测试 extended_euclid 函数
    testmod(name="greatest_common_divisor", verbose=True)  # 测试 greatest_common_divisor 函数

"""
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    